# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 2.dynamic_programming_fibonacci.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2021/11/19 11:22
------------------------------------------
"""


def bad_fibo(n):
    """
        时间复杂度爆炸的菲波那切数列
    """

    if n == 1 or n == 2:
        return 1

    return bad_fibo(n - 1) + bad_fibo(n - 2)


def helper(memo: dict, n: int):
    """
        动态规划思想下的菲波那切数列所需的“备忘录”
        用“备忘录”记录重叠子问题的计算结果，避免重复计算

        不过这种还不是真正的动态规划迭代，这种是自顶向下（从规模大的问题逐渐分解规模），真正的迭代动态规划是自底向上，
        这也是动态规划一般都脱离递归，而是由循环迭代完成计算
    """
    if n == 1 or n == 2:
        return 1

    elif n in memo:
        return memo[n]

    memo[n] = helper(memo, n - 1) + helper(memo, n - 2)

    return memo[n]


def good_fibo(n):
    if n < 1:
        return 0

    memo = dict()

    return helper(memo, n)


def dp_fibo(n):
    """
        dp 字典的迭代解法
    """
    dp = dict()
    dp[1] = dp[2] = 1

    for i in range(2, n + 1):
        v1, v2 = i - 1, i - 2
        dp[i] = dp[v1] + dp[v2]

    return dp[n]


def fibo_pro(n: int):
    """
        根据斐波那契数列 的状态转移⽅程，
        当前状态只和之前的两个状态有关，
        其实并不需要那么⻓ 的⼀个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就⾏
    """
    if n == 1 or n == 2:
        return 1

    prev = 1
    curr = 2

    for i in range(3, n + 1):
        sum_ = prev + curr
        prev = curr
        curr = sum_

    return curr


if __name__ == '__main__':
    # print(good_fibo(8))
    print(fibo_pro(3))
